package main

import (
	"fmt"
	"time"
)

type FibonacciFunc func(int) int

// 斐波那契数列  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...
func fibonacci(n int) int {
	if n == 1 {
		return 0
	}
	if n == 2 {
		return 1
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

const MAX = 50
var fibs [MAX]int

// 缓存中间结果的递归函数优化版
// 通过缓存中间计算结果来避免重复计算，从而提升递归函数的性能。
func fibonacci2(n int) int {
	if n == 1 {
		return 0
	}

	if n == 2 {
		return 1
	}

	index := n - 1
	if fibs[index] != 0 {
		return fibs[index]
	}

	num := fibonacci2(n-1) + fibonacci2(n-2)
	fibs[index] = num
	return num
}
// 通过尾递归优化递归函数性能
/**
函数调用底层是通过栈来维护的，对于递归函数而言，如果层级太深，同时保存成百上千的调用记录，会导致这个栈越来越大，
消耗大量内存空间，严重情况下会导致栈溢出（stack overflow），为了优化这个问题，可以引入尾递归优化技术来重用栈，
降低对内存空间的消耗，提升递归函数性能。

尾调用是指一个函数的最后一个动作是调用一个函数（只能是一个函数调用，不能有其他操作，比如函数相加、乘以常量等）
若这个函数在尾位置调用自身，则称这种情况为尾递归

尾调用的一个重要特性是它不是在函数调用栈上添加一个新的堆栈帧 —— 而是更新它，尾递归自然也继承了这一特性，
这就使得原来层层递进的调用栈变成了线性结构，因而可以极大优化内存占用，提升程序性能，这就是尾递归优化技术。
 */
func fibonacci3(n int) int {
	return fibonacciTail(n, 0, 1) // F(1) = 0, F(2) = 1
}
// 当前 first + second 的和赋值给下次调用的 second 参数，当前 second 值赋值给下次调用的 first 参数，
// 就等同于实现了 F(n) = F(n-1) + F(n-2) 的效果，循环往复，不断累加，直到 n 值等于 1（F(1) = 0，无需继续迭代下去），
// 则返回 first 的值，也就是最终的 F(n) 的值。
func fibonacciTail(n, first, second int) int {
	if n < 2 {
		return first
	}
	return fibonacciTail(n-1, second, first+second)
}


// 斐波那契函数执行耗时计算 （装饰器模式）
func fibonacciExecTime(f FibonacciFunc) FibonacciFunc {
	return func(n int) int {
		start := time.Now() // 起始时间
		num := f(n)  // 执行斐波那契函数
		end := time.Since(start) // 函数执行完毕耗时
		fmt.Printf("--- 执行耗时: %v ---\n", end)
		return num  // 返回计算结果
	}
}